using System;
using System.Collections.Generic;

using FineCollection.Intf;


using math = System.Math;
using arrays = System.Array;


namespace FineCollection.Const
{
    /// <summary>
    /// Immutable set. 
    /// All items are different, nulls are not allowed.
    /// </summary>
    /// <typeparam name="T">type of an item.</typeparam>
    public class ConstSortSet<T> : ConstSet<T>, RRandomSet<T>
        where T: IComparable<T>
    {

        private static readonly IComparer<T> comparer = Comparer<T>.Default;



        #region CONSTRUCTORS

        /// <summary>
        /// Temporary data object for constant fields initialization.
        /// </summary>
        /// <stereotype>transfer object</stereotype>
        private struct ConstructionData
        {
            internal T[] arr;
            internal int count;
        }



        /// <summary>
        /// Constructs a constant sorted set by the given data.
        /// </summary>
        /// <param name="firstIndex">firts index (origin).</param>
        /// <param name="array">array with items to make set of.</param>
        /// <param name="count">count of items in the array.</param>
        /// <param name="resort">array needs to be resorted.</param>
        /// <param name="removeDuplicates">array can contain duplicates.</param>
        /// <param name="takeOwnership">take ownership of this array.</param>
        internal ConstSortSet(int  firstIndex, 
                              T[]  array, 
                              int  count, 
                              bool resort,
                              bool removeDuplicates,
                              bool takeOwnership)
            : this(firstIndex, PrepareData(array,count,resort,removeDuplicates,takeOwnership))
        { }


        private ConstSortSet(int firstIndex, ConstructionData cdata) 
            : base(firstIndex, cdata.arr, cdata.count, true)
        { }


        private static ConstructionData PrepareData(T[]  array, 
                                                    int  count, 
                                                    bool resort,
                                                    bool removeDuplicates,
                                                    bool takeOwnership)
        {
            ConstructionData cdata = new ConstructionData 
                                {
                                arr = takeOwnership ? array : new T[count], 
                                count = count
                                };

            if (!takeOwnership)
                System.Array.Copy(array, cdata.arr, cdata.count);

            if (count >= 2)
            {
                if (resort)
                    System.Array.Sort(cdata.arr, 0, count);
                if (removeDuplicates)
                    RemoveDuplicates(cdata.arr, ref cdata.count);
            }

            return cdata;
        }


        private static void RemoveDuplicates(T[] arr, ref int count)
        {
            int i = count - 1;
            while (i >= 1)
            {
                if (comparer.Compare(arr[i-1], arr[i]) == 0)
                {
                    count--;
                    if (i < count)
                        System.Array.Copy(arr, i+1, arr, i, count - i);
                    arr[count] = default(T); 
                }
                else
                {
                    i--;
                }
            }
        }


        #endregion



        #region RORDERSET AND RRANDOMSET MEMBERS


        IComparer<T> ROrderSet<T>.Comparer
        {
            get { return comparer; }
        }



        /// <summary>
        /// Looks for the specified item, 
        /// or for the possible position where this item may be placed
        /// if this item is not in the collection.
        /// </summary>
        /// <param name="item">an item to look for, must not be null.</param>
        /// <param name="found">true if found, false otherwise.</param>
        /// <param name="position">
        /// <ul>
        /// <li>if the item is found - the position of this item;</li>
        /// <li>if the item is not found and the set is not empty -
        ///        the position of the nearest item larger than the specified one;</li>
        /// <li>if all items of the set are less than the specified one - 
        ///        the <see cref="RRandomList{T}.LastIndex"/> + 1;</li>
        /// <li>if the set is empty - 
        ///        the <see cref="RRandomList{T}.FirstIndex"/>.</li>
        /// </ul>
        /// </param>
        /// <exception cref="NullItemsException">when the specified item is null.</exception>
        public void Find(T item, out bool found, out int position)
        {
            if (item == null)
                throw new NullItemsException();

            if (IsEmpty)
            {
                found = false;
                position = firstIndex;
                return;
            }

            int index = arrays.BinarySearch(arr, 0, count, item);

            found = index >= 0;
            position = firstIndex + (found ? index : ~index);
        }


        /// <summary>
        /// Looks for the specified item.
        /// </summary>
        /// <param name="item">an item to look for, may be null.</param>
        /// <returns>index of the found item, 
        ///          or <see cref="int.MinValue"/> if not found.</returns>
        /// <remarks>
        /// <para>
        /// Uses the binary search algorithm,
        /// so its complexity is <i>o(ln(n))</i>.
        /// </para>
        /// <para>
        /// When the specified item is null or the set is empty - 
        /// does nothing and returns <see cref="int.MinValue"/>.
        /// </para>
        /// </remarks>
        public override int IndexOf(T item)
        {
            if (item == null)
                return int.MinValue;

            bool found;
            int position;

            Find(item, out found, out position);

            return found ? position : int.MinValue;
        }


        /// <summary>
        /// Creates a read-only ordered iterator.
        /// </summary>
        /// <returns>ordered iterator.</returns>
        /// <seealso cref="ROrderIterator{T}"/>
        new public ROrderIterator<T> TakeIterator()
        {
            return new OrderIterator<T>(this);
        }



        private class OrderIterator<TT> : ConstArray<T>.ArrIterator<TT>, ROrderIterator<TT>
            where TT : IComparable<TT>
        {
            private static readonly IComparer<TT> comparer =
                ConstSortSet<TT>.comparer;


            OrderIterator(ConstSortSet<TT> ia, int index) 
                : base(ia, index)
            {}

            internal OrderIterator(ConstSortSet<TT> ia) 
                : base(ia)
            {}


            public JumpResult Jump(TT item)
            {
                if (item == null)
                    throw new NullItemsException();

                if (inBounds)
                {
                    int z = comparer.Compare(item,Current);
                    if (z < 0) return JumpResult.Before;
                    if (z == 0) return JumpResult.Exactly;
                }

                if (index >= ia.count)
                {
                    return JumpResult.End;
                }

                int jumpIndex = arrays.BinarySearch(ia.arr, index + 1, ia.count - index - 1, item);

                if (jumpIndex >= 0)
                {
                    index = jumpIndex;
                    inBounds = true;
                    return JumpResult.Exactly;
                }
                else
                {
                    index = ~jumpIndex;
                    inBounds = index < ia.count;
                    return inBounds ? JumpResult.Over : JumpResult.End;
                }
            }


            RIterator<TT> RIterator<TT>.Clone()
            {
                return new OrderIterator<TT>(ia as ConstSortSet<TT>, index);
            }
        }


        #endregion



        #region OPERATORS

        public static ConstSortSet<T> operator * (ConstSortSet<T> setA, ConstSortSet<T> setB)
        {
            return CC.Intersect(setA.firstIndex, setA, setB);
        }


        /*
        public static ConstSortSet<T> operator * (ConstSortSet<T> setA, ROrderSet<T> setB)
        {
            return CC.Intersect(setA.firstIndex, setA, setB);
        }


        public static ConstSortSet<T> operator * (ROrderSet<T> setA, ConstSortSet<T> setB)
        {
            RRandomSet<T> randomSetA = setA as RRandomSet<T>;
            int theFirstIndex = randomSetA != null ? randomSetA.FirstIndex : setB.firstIndex;

            return CC.Intersect(theFirstIndex, setA, setB);
        }   
        */


        public static ConstSortSet<T> operator + (ConstSortSet<T> setA, ConstSortSet<T> setB)
        {
            return CC.Union(setA.firstIndex, setA, setB);
        }


        /*
        public static ConstSortSet<T> operator + (ConstSortSet<T> setA, ROrderSet<T> setB)
        {
            return CC.Union(setA.firstIndex, setA, setB);
        }


        public static ConstSortSet<T> operator + (ROrderSet<T> setA, ConstSortSet<T> setB)
        {
            RRandomSet<T> randomSetA = setA as RRandomSet<T>;
            int theFirstIndex = randomSetA != null ? randomSetA.FirstIndex : setB.firstIndex;

            return CC.Union(theFirstIndex, setA, setB);
        }
        */


        public static ConstSortSet<T> operator - (ConstSortSet<T> minuend, ConstSortSet<T> subtrahend)
        {
            return CC.Difference(minuend.firstIndex, minuend, subtrahend);
        }


        #endregion


    }
}